package cn.chencq.collection.map;

public class MyHashMap2 {

	private MyEntry2[] arr;

	private int size;

	private int maxSize;

	static final int DEFAULT_INITIAL_CAPACITY = 16;

	public MyHashMap2() {
		this(DEFAULT_INITIAL_CAPACITY);
	}

	public MyHashMap2(int initialCapacity) {
		if (initialCapacity < 0) {
			try {
				throw new Exception();
			} catch (Exception e) {
				e.printStackTrace();
			}
		}
		int capacity = 1;
		if (capacity < initialCapacity) {
			capacity <<= 1;
		}
		this.maxSize = (int) (capacity * 0.75);

		this.arr = new MyEntry2[capacity];
	}

	private int hash(int h) {
		h ^= (h >>> 20) ^ (h >>> 12);
		return h ^ (h >>> 7) ^ (h >>> 4);
	}

	private int indexFor(int h, int length) {
		return h & (length - 1);
	}

	public int size() {
		return this.size;
	}

	public boolean isEmpty() {
		return size == 0;
	}

	public Object put(Object key, Object value) {
		if (key == null) {
			return putForNullKey(value);
		}
		int hash = hash(key.hashCode());
		int i = indexFor(hash, arr.length);

		for (MyEntry2 e = arr[i]; e != null; e = e.next) {
			Object k;
			if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
				Object oldValue = e.value;
				e.value = value;
				return oldValue;
			}
		}
		addMyEntry(hash, key, value, i);
		return null;
	}

	private Object putForNullKey(Object value) {
		for (MyEntry2 e = arr[0]; e != null; e = e.next) {
			if (e.key == null) {
				Object oldValue = e.value;
				e.value = value;
				return oldValue;
			}
		}
		addMyEntry(0, null, value, 0);
		return null;
	}

	public Object get(Object key) {
		if (key == null) {
			return getForNullKey();
		}
		int hash = hash(key.hashCode());
		int i = indexFor(hash, arr.length);

		for (MyEntry2 e = arr[i]; e != null; e = e.next) {
			Object k;
			if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
				return e.value;
			}
		}
		return null;
	}

	private Object getForNullKey() {
		for (MyEntry2 e = arr[0]; e != null; e = e.next) {
			if (e.key == null) {
				return e.value;
			}
		}
		return null;
	}

	public MyEntry2 getEntry2(Object key) {
		int hash = key == null ? 0 : hash(key.hashCode());
		int i = indexFor(hash, arr.length);

		for (MyEntry2 e = arr[i]; e != null; e = e.next) {
			Object k;
			if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {
				return e;
			}
		}
		return null;
	}

	public Object remove(Object key) {
		MyEntry2 e = removeMyEntry(key);
		return e == null ? null : e.value;
	}

	public boolean containsKey(Object key) {
		return getEntry2(key) != null;
	}

	public boolean containsValue(Object value) {

		return false;
	}

	public void resize(int newCapacity) {
		MyEntry2[] oldArr = arr;
		int oldCapacity = oldArr.length;

		MyEntry2[] newArr = new MyEntry2[newCapacity];
		transfer(newArr);
		arr = newArr;
		maxSize = (int) (newCapacity * 0.75);
	}

	private void transfer(MyEntry2[] newArr) {
		MyEntry2[] src = arr;
		int newCapacity = newArr.length;
		for (int j = 0; j < src.length; j++) {
			MyEntry2 e = src[j];
			if (e != null) {
				src[j] = null;
				do {
					MyEntry2 next = e.next;
					int i = indexFor(e.hash, newCapacity);
					e.next = newArr[i];
					newArr[i] = e;
					e = next;
				} while (e != null);
			}
		}
	}

	public void clear() {
		MyEntry2[] tab = arr;
		for (int i = 0; i < tab.length; i++)
			tab[i] = null;
		size = 0;
	}

	public MyEntry2 removeMyEntry(Object key) {
		int hash = (key == null) ? 0 : hash(key.hashCode());
		int i = indexFor(hash, arr.length);
		MyEntry2 prev = arr[i];
		MyEntry2 e = prev;
		while (e != null) {
			MyEntry2 next = e.next;
			Object k;
			if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {
				size--;
				if (prev == e) {
					arr[i] = next;
				} else {
					prev.next = next;
				}
				return e;
			}
			prev = e;
			e = next;
		}
		return e;
	}

	public void addMyEntry(int hash, Object key, Object value, int index) {
		MyEntry2 e = arr[index];

		arr[index] = new MyEntry2(key, value, hash, e);

		if (size++ >= maxSize) {
			resize(2 * arr.length);
		}
	}

	public void creatMyEntry(int hash, Object key, Object value, int index) {
		MyEntry2 e = arr[index];
		arr[index] = new MyEntry2(key, value, hash, e);
		size++;
	}

	class MyEntry2 {
		final Object key;
		private Object value;
		final int hash;// hash?

		private MyEntry2 next;

		public MyEntry2(Object key, Object value, int hash, MyEntry2 next) {
			this.key = key;
			this.value = value;
			this.hash = hash;
			this.next = next;
		}

		public final Object getKey() {
			return key;
		}

		public final Object getValue() {
			return value;
		}

		public final Object setValue(Object newValue) {
			Object oldValue = value;
			value = newValue;
			return oldValue;
		}

		public final boolean equals(Object o) {
			if (!(o instanceof MyEntry2)) {
				return false;
			}
			MyEntry2 e = (MyEntry2) o;
			Object k1 = getKey();
			Object k2 = e.getKey();
			if (k1 == k2 || (k1 != null && k1.equals(k2))) {
				Object v1 = getValue();
				Object v2 = e.getValue();
				if (v1 == v2 || (v1 != null && v1.equals(v2)))
					return true;
			}
			return false;
		}

		public final int hashCode() {
			return (key == null ? 0 : key.hashCode()) ^ (value == null ? 0 : value.hashCode());
		}

		public final String toString() {
			return getKey() + "=" + getValue();
		}

	}

	public static void main(String[] args) {
		MyHashMap2 m = new MyHashMap2(2);
		m.put("aa", 11);
		m.put("bb", 22);
		m.put("cc", 33);
		m.put("dd", 44);
		m.put("ee", 11);
		m.put("ff", 22);
		m.put("gg", 33);
		m.put("hh", 44);
		m.put("ii", 11);
		m.put("jj", 22);
		m.put("kk", 33);
		m.put("ll", 44);
		System.out.println(m.get("aa"));
		m.put("dd", 55);
		System.out.println(m.get("dd"));

		System.out.println(m.size());
	}
}